//测试红黑树代码是否正确
public class Test {
    //判断是否存在两个连续的红色结点
    private static boolean isTowRedNodes(TreeNode root) {
        if(root == null) {
            return true;
        }

        if(root.color == Color.RED) {
            if(root.parent.color == Color.RED) {
                System.out.println("出现两个连续的红色结点！！！");
                return false;
            }
        }

        return isTowRedNodes(root.left) && isTowRedNodes(root.right);
    }

    //判断路径上的黑色结点是否相同
    private static boolean pathBlackNodes(TreeNode root,int pathBlack,int black) {
        if(root == null) {
            return true;
        }

        if(root.color == Color.BLACK) {
            pathBlack++;
        }

        if(root.left == null && root.right == null) {
            if(pathBlack > black) {
                return false;
            }
        }

        return pathBlackNodes(root.left,pathBlack,black) && pathBlackNodes(root.right,pathBlack,black);
    }

    //中序遍历是否有序
    private static void isSort(TreeNode root) {
        if(root == null) {
            return;
        }
        isSort(root.left);
        System.out.print(root.val + " ");
        isSort(root.right);
    }

    //检验红黑树
    private static boolean isRBTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(root.color != Color.BLACK){
            return false;
        }

        int black = 0;
        TreeNode cur = root;
        while(cur != null) {
            if(cur.color == Color.BLACK) {
                black++;
            }
            cur = cur.left;
        }

        return isTowRedNodes(root) && pathBlackNodes(root,0,black);
    }

    public static void main(String[] args) {
        RedBlackTree redBlackTree = new RedBlackTree();
        int[] arr = {4,2,6,1,3,5,15,7,16,14};
        for (int i = 0; i < arr.length; i++) {
            redBlackTree.insert(arr[i]);
        }

        isSort(redBlackTree.root);
        System.out.println(isRBTree(redBlackTree.root));
    }
}
